package wiggleSortII;


public class Solution {
    public void wiggleSort(int[] nums) {
        int mid,left=Integer.MAX_VALUE,right=Integer.MIN_VALUE;
        if (nums.length <= 1) {
            return;
        }
        for (int i=0;i<nums.length;i++){
        	if (nums[i]>right) right=nums[i];
        	if (nums[i]<left) left=nums[i];
        }
        while (true){
        	mid = (left < 0 && right > 0) ? (left + right) / 2 : left + (right - left) / 2;
        	int small=0,big=0,eq=0;
            for (int i=0;i<nums.length;i++){
            	if (nums[i]>mid) big++;
            	if (nums[i]<mid) small++;
            	if (nums[i]==mid) eq++;
            }
            if (small==big) break;
            if ((small+eq>=nums.length/2)&&(small<nums.length/2)) break;
            if ((big+eq>=nums.length/2)&&(big<nums.length/2)) break;
            if (small<big) left=mid;
            else right=mid;
            
        }
        mid=(left+right)/2;
        int p=mid;
        final int n = nums.length;
        int m = 0, r = nums.length - 1;
        int lw = 1, mw = 1, rw = (1 + 2 * (nums.length - 1)) % (n | 1);
        while (m <= r) {
            if (nums[mw] > p) {
                int tmp = nums[mw];
                nums[mw] = nums[lw];
                nums[lw] = tmp;
                mw = (mw + 2) % (n | 1);
                ++m;
                lw = (lw + 2) % (n | 1);
            } else if (nums[mw] < p) {
                int tmp = nums[mw];
                nums[mw] = nums[rw];
                nums[rw] = tmp;
                rw = (rw - 2 + (n | 1)) % (n | 1);
                --r;
            } else {
                mw = (mw + 2) % (n | 1);
                ++m;
            }
        }
    }
	public static void main(String args[]){
		Solution so=new Solution();
		int[] nums={1,3,2,2,3,1};
		so.wiggleSort(nums);
	}
}
/*324. Wiggle Sort II
 * 题目大义:长度为n序列，生成nums[0] < nums[1] > nums[2] < nums[3]....的形式（妈的智障）
 * 核心：中位数
 * 二分求中位数
 * 大于中位数的放于1,3,5位置
 * 小于中位数的放于0,2,4位置
 * 等于中位数的最后插入空余位置
 * PS：反正我只能完成O(N)时间+O(n)空间
 * O(1)空间什么的迷得一B。。有空再玩
 */
